/*
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。
输入: [1,3,5,6], 5
输出: 2

输入: [1,3,5,6], 7
输出: 4

输入: [1,3,5,6], 0
输出: 0
*/

int searchInsert(int* nums, int numsSize, int target){
    int l = 0, r = numsSize-1;
    if (nums[numsSize - 1] < target) return numsSize;
    
    while (l < r) {
        int m = (l + r) / 2;    // 中间偏左
        if (nums[m] < target) l = m + 1;    // 不会超过r
        else r = m;
    }

    return l;
}